//
// Created by xili on 2024/8/29 11:16.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int> &arr, int k) {
        int n = arr.size();
        double low = 0.0, high = 1.0;
        vector<int> res(2);
        while (true) {
            double mid = (low + high) / 2.0;
            int total = 0;
            int i = 0;
            int p = 0, q = 1;
            for (int j = 1; j < n; ++j) {
                while (i < j && arr[i] < mid * arr[j]) {
                    ++i;
                }
                total += i;

                if (i > 0 && arr[i - 1] * q > arr[j] * p) {
                    p = arr[i - 1];
                    q = arr[j];
                }
            }
            if (total == k) {
                res[0] = p;
                res[1] = q;
                break;
            } else if (total < k) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return res;
    }
};
